- Бинарное отношение
-
В математике бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется непустое множество упорядоченных пар элементов этого множества.
Содержание
Связанные определения
- называют бинарным отношением на множестве , если . При этом вместо записи часто используют запись
- Если то говорят, что определено на паре множеств и .
- Множество всех первых элементов пар из называется областью определения отношения и обозначается как .
- Множество всех вторых элементов пар из называется областью значения отношения и обозначается как .
- Инверсия(Обратное отношение) — это множество и обозначается, как .
- Композиция (суперпозиция) бинарных отношений и — это множество и обозначается, как .
Свойства отношений
Бинарные отношения могут обладать различными свойствами, такими как
- Рефлексивность: .
- Антирефлексивность (иррефлексивность): .
- Симметричность: .
- Антисимметричность: .
- Транзитивность: .
- Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
Виды отношений
- Рефлексивное транзитивное отношение называется отношением квазипорядка.
- Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.
- Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.
- Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
- Полное антисимметричное (для любых x, y выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка.
- Антирефлексивное асимметричное отношение называется отношением доминирования.
Виды двухместных отношений
- Обратное отношение[уточнить] (отношение, обратное к R) — это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R−1. Для данного отношения и обратного ему верно равенство: (R−1)−1 = R.
- Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
- Рефлексивное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любого х этого множества элемент х находится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство, одновременность, сходство.
- Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отношении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
- Транзитивное отношение — двухместное отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
- Нетранзитивное отношение[уточнить] — двухместное отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
- Симметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
- Антисимметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR−1y следует х = у (то есть R и R−1 выполняются одновременно лишь для равных между собой членов).
- Асимметричное отношение[уточнить] — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
- Отношение эквивалентности (отношение тождества[уточнить], отношение типа равенства) — двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям):
- аксиоме рефлексивности (см. выше): xRx (предмет находится в отношении R к самому себе);
- аксиоме симметричности (см. выше): xRyyRx (если предмет х находится в отношении R к предмету у, то и у находится в отношении R к х);
- аксиоме транзитивности (см. выше): xRy&yRzxRz (если предмет х находится в отношении R к предмету у и у находится в отношении R к z, то х находится в отношении R к z).
- Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке , подобие, одновременность. Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
- Отношения порядка — отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — «строгий» порядок.
- Функция — двухместное отношение R, определенное на некотором множестве, отличающееся тем, что каждому значению x отношения xRy соответствует лишь одно-единственное значение y. Пример: «y отец x». Свойство функциональности отношения R записывается в виде аксиомы: (xRy и xRz)→(y≡z). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y, но не наоборот.
- Биекция (одно-однозначное отношение) — двухместное отношение R, определенное на некотором множестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у, и каждому значению у соответствует единственное значение х. Одно-однозначное отношение является частным случаем однозначного отношения.
- Связанное отношение — это двухместное отношение R, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx). Пример: отношение «меньше» (<).
Операции над отношениями
Так как отношения, заданные на фиксированной паре множеств , , суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных ,
Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.
Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.
Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом.
Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .
Пусть теперь , . Произведением отношений , называется отношение такое, что
Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.
Например, рассмотрим отношение строгого порядка определённого на множестве натуральных чисел. Несложно заметить, что
Бинарные отношения и называются перестановочными, если . Несложно заметить, что для любого бинарного отношения , определённого на , , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.
Имеют место следующие тождества:
- ,
- ,
- ,
- ,
- ,
- ,
- .
Отметим, что аналоги последних двух тождеств для не имеют места.
Некоторые свойства отношения можно определить, используя операции над отношениями:
- Рефлексивность: ,
- Симметричность: ,
- Транзитивность: .
См. также
Литература
- А. И. Мальцев. Алгебраические системы. — М.: Наука, 1970.
Категории:- Теория множеств
- Дискретная математика
- Бинарные отношения
Wikimedia Foundation. 2010.